1. Field of the Invention
The present invention relates to a routing loop detection program that controls a computer to be operated as equipment for detecting routing loop and to routing loop detection method realized by a computer on which such a routing loop detection program is running.
2. Prior Art
As well known, IP (Internet Protocol) contained in TCP/IP (Transmission Control Protocol/Internet Protocol) suite is widely used as a Network layer protocol in the Internet, intranets, etc.
At least one IP address is given to the computer that has a communication function according to IP for individually identifying the computer from other computers.
When this kind of computer transmits data in the Network layer in the OSI (Open System Interconnection) reference model, the computer divides transmitting data into small data blocks called “packet” (it is also called “datagram”) in which a source IP address, a destination IP address and other information are included as a header information, and transmit the packet to a computer of the destination.
In general, this kind of computers are not directly connected to each other, they are connected through a plurality of computers that relay a packet specially. The relay specialty computer is called a router. IP addresses are also given to these routers, respectively.
Each router has a routing table that associates a destination IP address of a packet with IP addresses of other routers or computers that relay the packet. Receiving a packet from other routers or computers, the router selects the next router or computer to which the packet is transmitted and transmits the packet. Consequently, a packet is sent from the source computer to the destination computer through some routers in sequence.
Moreover, when a router receives a packet from another router or computer, the router decrements the residual hop number recorded on the predetermined field (a lifetime field in the IP version 4, a hop limit field in the IP version 6) of the IP header of the packet by one, increments the value in a checksum field by one as a result of the checksum calculation only for the IP version 4, and transmits the packet to the next router or computer. Furthermore, each router also discards packets whose residual hop number becomes zero and informs discard of the packet to the computer of the source IP address according to ICMP (Internet Control Message Protocol).
In general, the network that can perform packet communication according to IP in the Network layer by such a router and a computer is called an IP network.
Incidentally, routing loop is one of the network troubles caused in the IP network. The routing loop is a phenomenon in which a packet repeatedly travels among some routers and does not reach the destination.
In many cases, the routing loop is caused by various setup errors, troubles of hardware such as a router or other troubles. However, if the routing loop occurred in the predetermined router group is caused by the setting error of a router located outside the management area of the administrator who manages the router group, the administrator cannot resolve the routing loop because the administrator cannot check and change the setting of the router located outside the management area.
Then, it becomes important to quickly discover the router group that causes the routing loop in order to suppress the damage to the administrator suffering from the routing loop.
Conventionally, the following three methods were known to discover such routing loop.
The first method uses the routing table. That is, the first method finds out combinations of entry records that form loops one after another by checking the routing tables of all routers in the management area. An advantage of the first method is that a combination of routers forming a loop can be certainly detected.
The second method uses a traceroute. That is, the second method makes a computer having traceroute function connect to a router in the management area and makes the computer sequentially transmit investigating packets whose residual hop numbers are different one by one to another computer in the management area. If packets with time-exceeded message (the ICMP header whose type field is “11” is added to the IP header) are repeatedly received from the same router group located on the path to the destination address, the second method judges that routing loop occurs in that router group. An advantage of the second method is that routing loop caused in any path within the management area can be detected.
The third method uses a packet capture. That is, the third method inserts a computer that has a packet capturing function among the routers in the management area to supervise all the packets that pass through the routers. See “Routing Loop Detection” on page 3 of chapter 4 of “Detection and Analysis of Routing Loops in Packet Traces” by Urs Hengartner, Sue Moon, Richard Mortier, and Christophe Diot, whose URL is “http://www-2.cs.cmu.edu/People/uhengart/imw02.pdf” that could be browsed on Jun. 9, 2003.
According to the third method, the computer extracts packets whose contents are identical with the exception of the residual hop number (and checksum value in the case of the IP version 4) in the IP header. When the residual hop numbers (and the checksum number) of the extracted packets vary in arithmetic series, the computer judges that routing loop is caused. An advantage of the third method is that routing loop can be immediately detected.
However, since the first method requires the manual work for checking the combinations of the entry records, it takes much time to find the routing loop. Moreover, since the usual routing table includes many entry numbers (100 pieces, for example), the time and effort for finding routing loop increase as the number of the routers in the management area increases. Therefore, the first method lacks immediacy and scale extendibility.
Further, the second method mentioned above may not detect routing loop in the following case. Some mistakes in a routing table may occur the phenomenon where only the packet from a certain source IP address causes routing loop and the other packets do not cause routing loop. In such a case, routing loop may not be detected by the second method, even if investigating packets are supplied to the path. Moreover, since the second method requires a great number of investigating packets, the load given to the network traffic becomes greater as the investigation period becomes shorter. The load may cause a new network trouble. Therefore, the second method lacks certainty and immediacy.
Furthermore, although the third method can detect routing loop caused between the routers that straddle the packet capture, it cannot detect routing loop caused between the routers that do not straddle the packet capture. When the communication speed between routers increases, the number of packets that is acquired by the packet capture becomes too large to be caught up by the computer, which interferes with the application of the computer to large-scale and high-speed management area like iDC (internet Data Center) or ISP (Internet Service Provider). Therefore, the third method lacks certainty and scale extendibility.